1196F - K-th Path - CodeForces Solution

#include <bits/stdc++.h>

using namespace std;

typedef pair<long long, long long> Point;

#define ll long long
#define ff first
#define ss second
#define pb push_back
#define mk make_pair
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
#define MOD 1000000007
#define MOD1 1000000009
#define sqr(x) sqr((x)*(x))

void debug_out() { cerr << endl; }
template<typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << ' ' << H; debug_out(T...); }
#ifdef BE_DEBUG
#define debug(...) cerr << "\033[1;31m(" << #__VA_ARGS__ << "):\033[0m", debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif

const int N = 200005;

int n,m,k;
pair<int,pair<int,int>> p[N];
map<int,int> mp;
map<int,int> :: iterator it;
ll ans[850][850];
vector<ll> tmp;

int main() {
    IOS
    cin >> n >> m >> k;
    for(int i = 1; i <= m; i ++) {
        cin >> p[i].ss.ff >> p[i].ss.ss >> p[i].ff;
    }
    sort(p + 1, p + m + 1);
    for(int i = 1; i <= k; i ++) {
        mp[p[i].ss.ff] ++;
        mp[p[i].ss.ss] ++;
    }
    int cnt = 0;
    for(it = mp.begin(); it != mp.end(); it ++) {
        mp[it -> ff] = cnt;
        cnt ++;
    }
    for(int i = 1; i <= k; i ++) {
        p[i].ss.ff = mp[p[i].ss.ff];
        p[i].ss.ss = mp[p[i].ss.ss];
        //
        ans[p[i].ss.ff][p[i].ss.ss] = p[i].ff; 
        ans[p[i].ss.ss][p[i].ss.ff] = p[i].ff;
        // cout << p[i].ss.ff << ' ' << p[i].ss.ss << ' ' << p[i].ff << '\n';
    }
    for(int k = 0; k < cnt; k ++) {
        for(int i = 0; i < cnt; i ++) {
            for(int j = 0; j < cnt; j ++) {
                if(ans[i][k] == 0 || ans[k][j] == 0) continue;
                if(ans[i][j] == 0) ans[i][j] = ans[i][k] + ans[k][j];
                else ans[i][j] = min(ans[i][j], ans[i][k] + ans[k][j]);
            }
        }
    }
    for(int i = 0; i < cnt; i ++) {
        for(int j = i + 1; j < cnt; j ++) {
            if(ans[i][j] != 0) tmp.pb(ans[i][j]);
        }
    }
    sort(tmp.begin(), tmp.end());
    cout << tmp[k - 1];
    return 323/1001;
}